package sit.engreal.leetcode.problems900;

import org.junit.jupiter.api.Assertions;

/**
 * <a href="https://leetcode.cn/problems/score-of-parentheses/">856. 括号的分数</a>
 */
public class LeetCode856 {
    public int scoreOfParentheses(String s) {
        return S(s, new int[]{0});
    }

    /**
     * S -> (S) S | empty
     */

    public int S(String s, int[] a) {
        final int i = a[0];
        if (s.length() <= i) {
            return 0;
        }
        if (s.charAt(i) == ')') {
            return 0;
        }

        a[0] += 1;
        int v = S(s, a);
        if (v == 0) {
            v = 1;
        } else {
            v *= 2;
        }
        a[0] += 1;
        v += S(s, a);
        return v;
    }

    public static void main(String[] args) {
        final LeetCode856 demo = new LeetCode856();

        Assertions.assertEquals(1, demo.scoreOfParentheses("()"));
        Assertions.assertEquals(2, demo.scoreOfParentheses("(())"));
        Assertions.assertEquals(2, demo.scoreOfParentheses("()()"));
        Assertions.assertEquals(6, demo.scoreOfParentheses("(()(()))"));
    }
}
